package leetcode.weekly.week339;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

//Solution4Test
public class Solution4 {

	public int[] minReverseOperations(int n, int p, int[] banned, int k) {
		int[] ans = new int[n];
		Arrays.fill(ans, -1);
		ans[p] = 0;
		Set<Integer> set = new HashSet<>();
		for (int i : banned) {
			set.add(i);
		}
		Queue<Integer> queue = new LinkedList<>();
		queue.add(p);
		int cnt = 1;
		while (!queue.isEmpty()) {
			int size = queue.size();
			while (size > 0) {
				int cur = queue.poll();
				int r = Math.min(cur + k - 1, n - 1);
				for (int i = r; i >= cur; i--) {
					if (i - k + 1 < 0) {
						break;
					}
					int dist = i - cur + 1;
					int diff = k - dist;
					int to = i - diff;
					if (ans[to] != -1) {
						break;
					}
					if (to >= 0 && to < n && !set.contains(to) && ans[to] == -1) {
						queue.add(to);
						ans[to] = cnt;
					}
				}
				size--;
			}
			cnt++;
		}
		return ans;
	}
}
